package 每日一题;

import java.util.*;

/**
 * @author 会玩的洋洋
 * https://leetcode.cn/problems/remove-sub-folders-from-the-filesystem/
 */
public class _1233_删除子文件夹 {
    /**
     * 执行用时：55ms，内存消耗：50MB
     * @param folder
     * @return
     */
    public List<String> removeSubfolders(String[] folder) {
        List<String> ans = new ArrayList<>();
        Arrays.sort(folder);
        ans.add(folder[0]);
        int n = folder.length;
        for (int i = 1; i < n; i++) {
            int pre = ans.get(ans.size() - 1).length();
            if (!(pre < folder[i].length() && ans.get(ans.size() - 1).equals(folder[i].substring(0, pre)) && folder[i].charAt(pre) == '/')) {
                ans.add(folder[i]);
            }
        }
        return ans;
    }

    /**
     * 执行用时：99ms，内存消耗：63MB
     * @param folder
     * @return
     */
    public List<String> removeSubfolders2(String[] folder) {
        Trie root = new Trie();
        for (int i = 0; i < folder.length; i++) {
            List<String> path = split(folder[i]);
            Trie cur = root;
            for (String name : path) {
                cur.children.putIfAbsent(name, new Trie());
                cur = cur.children.get(name);
            }
            cur.ref = i;
        }

        List<String> ans = new ArrayList<>();
        dfs(folder, ans, root);
        return ans;
    }

    private List<String> split(String s) {
        List<String> ret = new ArrayList<>();
        StringBuilder cur = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '/') {
                ret.add(cur.toString());
                cur.setLength(0);
            } else {
                cur.append(c);
            }
        }
        ret.add(cur.toString());
        return ret;
    }

    private void dfs(String[] folder, List<String> ans, Trie cur) {
        if (cur.ref != -1) {
            ans.add(folder[cur.ref]);
            return;
        }
        for (Trie child : cur.children.values()) {
            dfs(folder, ans, child);
        }
    }
}

class Trie {
    int ref;
    Map<String, Trie> children;

    public Trie() {
        ref = -1;
        children = new HashMap<>();
    }
}
